package sort;


import java.util.Arrays;

/**
 * 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
        test(800000);

    }


    //选择排序
    public static void selectSort(int[] arr){

        //假定第一个数是最小的
        for (int i = 0; i <arr.length-1 ; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j <arr.length ; j++) {
                if(min>arr[j]){  //如果后面有值比指定的min小
                    min = arr[j];
                    minIndex = j;
                }
            }
            //找到了最小值
            if(minIndex !=i){//说明不能是自己
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }

//        System.out.println("选择排序："+Arrays.toString(arr));
    }

    //冒泡排序
    public static void bubbleSort(int[] arr){
        int temp = 0; //临时变量
        boolean flag = false;  //标识变量,表示是否进行交换
        for (int j = 0; j <arr.length-1 ; j++) {
            for (int i = 0; i <arr.length-1-j ; i++) {
                if(arr[i]>arr[i+1]){
                    flag = true;
                    temp  = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            //优化代码
            if(flag == false){
                System.out.println("冒泡排序："+Arrays.toString(arr));
                break;
            }else {

                flag = false;  //需要把flag标志位改变，继续进行判断
            }
        }


    }

    //插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i <arr.length ; i++) {
            int insertVal = arr[i];  //数组的第二个数据
            int insertIndex = i-1;  //第二个数据的前一个索引

            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex]; //把前面那个数后移
                insertIndex--;
            }
            if(insertIndex+1 !=i){
                arr[insertIndex +1] = insertVal;
            }

        }
        //System.out.println("插入排序："+Arrays.toString(arr));
    }

    //希尔排序(交换法)
    public static void shellSort(int[] arr){
        int temp = 0;
        for (int gap = arr.length/2; gap >0 ; gap /=2) {  //进行分组
            for (int i = gap; i <arr.length ; i++) {  //对分的每一组进行排序
                for (int j = i-gap; j >=0 ; j -=gap) {
                    if(arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }

        System.out.println("希尔排序："+Arrays.toString(arr));
    }

    //希尔排序（移位法）
    public static void shellSort1(int[] arr){
        for (int gap = arr.length/2; gap >0 ; gap /=2) {
            //从第gap个元素，逐个对其所在的组进行插入排序
            for (int i = gap; i <arr.length ; i++) {
                int j = i;  //待插入的下标
                int temp = arr[j];  //待插入的值
                if(arr[j] < arr[j-gap]){  //有个步长

                    while (j-gap>=0 && temp<arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j -=gap;
                    }

                    //当退出这个while后，就找到了插入的位置
                    arr[j] = temp;
                }
            }
        }
        //System.out.println("希尔排序："+Arrays.toString(arr));
    }

    //快速排序
    public static void quicksort(int[] arr,int left, int right){
        //记录左右索引
        int l = left;  //左下标
        int r = right; //右下标
        int pivot = arr[(left + right)/2];  //找到中轴线
        int temp = 0;  //作为交换时使用

        //比pivot小的放到左边
        //比pivot大的放到右边
        while (l < r){

            //在pivot的左边一直找，找到一个大于等于pivot
            while (arr[l]<pivot){
                l +=1;
            }
            while (arr[r] > pivot){
                r -=1;
            }
            //说明pivot的左右两边的值筛选完了
            if(l >=r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后发现arr[l]==pivot,往前移，不然会死循环
            if(arr[l] == pivot){
                r -=1;
            }

            //如果交换完后发现arr[r]==pivot，往后移
            if(arr[r] == pivot){
                l +=1;
            }
        }
        //如果l == r,必须l++,r--,否则栈溢出
        if(l == r){
            l +=1;
            r -=1;
        }
        //向左递归
        if(left<r){
            quicksort(arr,left,r);
        }

        //向右递归
        if(right>l){
            quicksort(arr,l,right);
        }
    }

    //测试两个运行时间
    public static void test(int num){
        int[] arry = new int[num];


        for (int i = 0; i <num ; i++) {
            arry[i] = (int)(Math.random()*80000);
        }
//        System.out.println("测试数组："+Arrays.toString(arry)+"\n");

        int[] test = new int[num];
        System.arraycopy(arry,0,test,0,num);

        int[] test1 = new int[num];
        System.arraycopy(arry,0,test1,0,num);

        int[] test2 = new int[num];
        System.arraycopy(arry,0,test2,0,num);

        int[] test3 = new int[num];
        System.arraycopy(arry,0,test3,0,num);

        int[] test4 = new int[num];
        System.arraycopy(arry,0,test4,0,num);


//        //选择排序
//        long startTime = System.currentTimeMillis();
//        selectSort(test);
//        long endTime = System.currentTimeMillis();
//        System.out.println("选择排序花费时间为："+(endTime-startTime)+"ms\n");


//        //冒泡排序
//        long startTime1 = System.currentTimeMillis();
//        bubbleSort(arry);
//        long endTime1 = System.currentTimeMillis();
//        System.out.println("冒泡排序花费时间为："+(endTime1-startTime1)+"ms\n");


//        //插入排序
//        long startTime2 = System.currentTimeMillis();
//        insertSort(test1);
//        long endTime2 = System.currentTimeMillis();
//        System.out.println("插入排序花费时间为："+(endTime2-startTime2)+"ms\n");

//        //希尔排序
//        long startTime3 = System.currentTimeMillis();
//        shellSort(test2);
//        long endTime3 = System.currentTimeMillis();
//        System.out.println("希尔排序（交换法）花费时间为："+(endTime3-startTime3)+"ms\n");

//        //希尔排序
//        long startTime4 = System.currentTimeMillis();
//        shellSort1(test3);
//        long endTime4 = System.currentTimeMillis();
//        System.out.println("希尔排序（移位法）花费时间为："+(endTime4-startTime4)+"ms\n");

        //快速排序
        long startTime5 = System.currentTimeMillis();
        quicksort(test4,0,test4.length-1);
        long endTime5 = System.currentTimeMillis();
        //System.out.println("快速排序："+Arrays.toString(arry));
        System.out.println("快速排序花费时间为："+(endTime5-startTime5)+"ms\n");
    }
}
